package solution.s_57;

/**
 * 解题思路：
 *      首先判断出新插入的区间与原有的区间是否有交集。
 *      假如没有交集，将新插入的区间插入到原来的区间列表中合适的位置返回。
 *      假如有交集，融合区间，然后将融合后的区间替换与新插入区间有交集的区间列表。
 */
public class Solution20201104 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][] {newInterval};
        }

        // 计算产生交集的开始和结束位置
        int startIndex = -1, endIndex = -1;
        for (int i = 0; i < intervals.length; i ++) {
            if (intervals[i][0] <= newInterval[1] && newInterval[0] <= intervals[i][1]) {
                // 产生交集
                // 假如此时 startIndex = -1，说明此时的 i 就是产生交集开始的位置
                if (startIndex == -1) {
                    startIndex = i;
                }
            } else {
                // 没有交集
                // 假如此时 startIndex != -1，此时 i-1 就是交集的最后位置
                if (startIndex != -1) {
                    endIndex = i - 1;
                    break;
                }
            }
        }

        // 假如此时 startIndex != -1 且 endIndex = -1，说明交集结束的位置就是最后的位置
        if (startIndex != -1 && endIndex == -1) {
            endIndex = intervals.length - 1;
        }

        // 没有交集
        if (startIndex == -1) {
            return noFixedInsert(intervals, newInterval);
        }

        // 有交集
        return fixedInsert(intervals, newInterval, startIndex, endIndex);
    }

    private int[][] noFixedInsert(int[][] intervals, int[] newInterval) {
        int[][] result = new int[intervals.length + 1][2];

        int i = 0;
        // 把比新插入区间小的区间放入结果中
        for (; i < intervals.length && newInterval[0] > intervals[i][0]; i ++) {
            result[i] = intervals[i];
        }

        // 把新插入的区间放进去
        result[i] = newInterval;

        // 假如新插入的区间不是最后一个，把后面的区间也拷贝进去
        if (i != result.length - 1) {
            System.arraycopy(intervals, i, result, i + 1, intervals.length - i);
        }

        return result;
    }

    private int[][] fixedInsert(int[][] intervals, int[] newInterval, int startIndex, int endIndex) {
        // 因为交集的开始和结束位置是 startIndex 和 endIndex，也就是说，从 startIndex 到 endIndex 位置的 (endIndex-startIndex+1) 个区间会变成一个区间
        // 所以结果的长度应该是 原长度-(endIndex-startIndex+1)+1
//        int[][] result = new int[intervals.length - (endIndex - startIndex + 1) + 1][2];
        int[][] result = new int[intervals.length - endIndex + startIndex][2];

        int i = 0;
        // 先将交集之前的区间加入结果集
        for (; i < startIndex; i ++) {
            result[i] = intervals[i];
        }

        // 将融合后的区间加入结果集
        newInterval[0] = Math.min(newInterval[0], intervals[startIndex][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[endIndex][1]);
        result[i] = newInterval;

        // 假如交集的结束位置不是最后一个元素，将后面的元素加入结果集
        if (endIndex != intervals.length - 1) {
            System.arraycopy(intervals, endIndex + 1, result, i + 1, intervals.length - endIndex - 1);
        }

        return result;
    }
}
